<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<title></title>
<!--Generated on Tue Jun  3 20:03:37 2014 by LaTeXML (version 0.7.999_04) http://dlmf.nist.gov/LaTeXML/.-->

<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<link rel="stylesheet" href="../../../../../../../LaTeXML.css" type="text/css">
<link rel="stylesheet" href="../../../../../../../ltx-article.css" type="text/css">
<link rel="stylesheet" href="../../../../../../../customRules.css" type="text/css">
</head>
<body>
<div class="ltx_page_main">
<div class="ltx_page_content">
<div class="ltx_document">
<div id="Sx1" class="ltx_section">
<h1 class="ltx_title ltx_title_section">Convolution</h1>

<div id="Sx1.p1" class="ltx_para">
<p class="ltx_p">A two-dimensional discrete convolution is defined as</p>
<table id="Sx1.E1" class="ltx_equation">

<tr class="ltx_equation ltx_align_baseline">
<td class="ltx_eqn_pad"></td>
<td class="ltx_align_center"><img id="Sx1.E1.m1" class="ltx_Math" style="vertical-align:-26px" src="mi/mi38.png" width="372" height="59" alt="\left(I*K\right)\left(x,y\right)=\sum_{-\infty}^{+\infty}\sum_{-\infty}^{+%
\infty}I\left(u,v\right)K\left(x-u,y-v\right)\,,"></td>
<td class="ltx_eqn_pad"></td>
<td rowspan="1" class="ltx_align_middle ltx_align_right"><span class="ltx_tag ltx_tag_equation">(1)</span></td>
</tr>
</table>
<p class="ltx_p">where <img id="Sx1.p1.m1" class="ltx_Math" style="vertical-align:-2px" src="mi/mi39.png" width="13" height="16" alt="I"> is an image of size <img id="Sx1.p1.m2" class="ltx_Math" style="vertical-align:-3px" src="mi/mi45.png" width="52" height="15" alt="m\times n">, and <img id="Sx1.p1.m3" class="ltx_Math" style="vertical-align:-2px" src="mi/mi41.png" width="20" height="16" alt="K"> is a convolution
kernel of arbitrary size. Values outside the domains of <img id="Sx1.p1.m4" class="ltx_Math" style="vertical-align:-2px" src="mi/mi39.png" width="13" height="16" alt="I"> and <img id="Sx1.p1.m5" class="ltx_Math" style="vertical-align:-2px" src="mi/mi41.png" width="20" height="16" alt="K">
are set to zero.
</p>
</div>
<div id="Sx1.p2" class="ltx_para">
<p class="ltx_p">Convolution can be a time demanding operation when implemented according
to the definition in Equation (<a href="#Sx1.E1" title="(1) ‣ Convolution" class="ltx_ref"><span class="ltx_text ltx_ref_tag">1</span></a>). To speed up the algorithms,
we use a method known as convolution with separable kernels. This
allows one to calculate the convolution of the image <img id="Sx1.p2.m1" class="ltx_Math" style="vertical-align:-2px" src="mi/mi39.png" width="13" height="16" alt="I"> with the
kernel <img id="Sx1.p2.m2" class="ltx_Math" style="vertical-align:-2px" src="mi/mi41.png" width="20" height="16" alt="K"> as</p>
<table id="Sx1.E2" class="ltx_equation">

<tr class="ltx_equation ltx_align_baseline">
<td class="ltx_eqn_pad"></td>
<td class="ltx_align_center"><img id="Sx1.E2.m1" class="ltx_Math" style="vertical-align:-6px" src="mi/mi37.png" width="196" height="25" alt="F=I*K=\left(I*\boldsymbol{k}\right)*\boldsymbol{k}^{\top}"></td>
<td class="ltx_eqn_pad"></td>
<td rowspan="1" class="ltx_align_middle ltx_align_right"><span class="ltx_tag ltx_tag_equation">(2)</span></td>
</tr>
</table>
<p class="ltx_p">if the kernel <img id="Sx1.p2.m3" class="ltx_Math" style="vertical-align:-2px" src="mi/mi41.png" width="20" height="16" alt="K"> can be written as <img id="Sx1.p2.m4" class="ltx_Math" style="vertical-align:-2px" src="mi/mi40.png" width="78" height="20" alt="K=\boldsymbol{k}\boldsymbol{k}^{\top}">.
Here the kernel <img id="Sx1.p2.m5" class="ltx_Math" style="vertical-align:-2px" src="mi/mi41.png" width="20" height="16" alt="K"> is an <img id="Sx1.p2.m6" class="ltx_Math" style="vertical-align:-3px" src="mi/mi7.png" width="37" height="18" alt="l\times l"> matrix and <img id="Sx1.p2.m7" class="ltx_Math" style="vertical-align:-6px" src="mi/mi44.png" width="156" height="26" alt="\boldsymbol{k}=\left[k_{1},k_{2},\ldots,k_{l}\right]^{\top}">.
Using the method of separable kernels reduces the time complexity
of the convolution from <img id="Sx1.p2.m8" class="ltx_Math" style="vertical-align:-8px" src="mi/mi43.png" width="77" height="25" alt="O\left(mnl^{2}\right)"> to <img id="Sx1.p2.m9" class="ltx_Math" style="vertical-align:-6px" src="mi/mi42.png" width="66" height="21" alt="O\left(mnl\right)">.</p>
</div>
<div id="Sx1.SSx1" class="ltx_subsection">
<h2 class="ltx_title ltx_title_subsection">See also</h2>

<div id="Sx1.SSx1.p1" class="ltx_para">
<ul id="I1" class="ltx_itemize">
<li id="I1.i1" class="ltx_item" style="list-style-type:none;">
<span class="ltx_tag ltx_tag_itemize">•</span> 
<div id="I1.i1.p1" class="ltx_para">
<p class="ltx_p"><a href="Filters.html" title="" class="ltx_ref">Image filtering and feature enhancement</a></p>
</div>
</li>
</ul>
</div>
</div>
</div>
</div>
</div>
<div class="ltx_page_footer">
<div class="ltx_page_logo">Generated  on Tue Jun  3 20:03:37 2014 by <a href="http://dlmf.nist.gov/LaTeXML/">LaTeXML <img src="" alt="[LOGO]"></a>
</div>
</div>
</div>
</body>
</html>
